SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Quadratic assignment problem</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Quadratic assignment problem</span></span>

</h1>

</header>

<p>The <b>quadratic assignment problem</b> (<b>QAP</b>) is one of the fundamental <a href="Combinatorial_optimization" title="Combinatorial optimization">combinatorial optimization</a> problems in the branch of <a href="Optimization_(mathematics)" class="mw-redirect" title="Optimization (mathematics)">optimization</a> or <a href="Operations_research" title="Operations research">operations research</a> in <a href="Mathematics" title="Mathematics">mathematics</a>, from the category of the <a href="Optimal_facility_location" title="Optimal facility location">facilities location</a> problems first introduced by Koopmans and Beckmann.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p><p>The problem models the following real-life problem:

</p>

<dl><dd>There are a set of <i>n</i> facilities and a set of <i>n</i> locations. For each pair of locations, a <i>distance</i> is specified and for each pair of facilities a <i>weight</i> or <i>flow</i> is specified (e.g., the amount of supplies transported between the two facilities). The problem is to assign all facilities to different locations with the goal of minimizing the sum of the distances multiplied by the corresponding flows.</dd></dl>

<p>Intuitively, the cost function encourages facilities with high flows between each other to be placed close together.

</p><p>The problem statement resembles that of the <a href="Assignment_problem" title="Assignment problem">assignment problem</a>, except that the <a href="Loss_function" title="Loss function">cost function</a> is expressed in terms of quadratic inequalities, hence the name.

</p>

<div class="mw-heading mw-heading2"><h2 id="Formal_mathematical_definition">Formal mathematical definition</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

<p>The formal definition of the quadratic assignment problem is as follows:

</p>

<dl><dd>Given two sets, <i>P</i> ("facilities") and <i>L</i> ("locations"), of equal size, together with a <a href="Weight_function" title="Weight function">weight function</a> <i>w</i> : <i>P</i> × <i>P</i> → <b><a href="Real_number" title="Real number">R</a></b> and a distance function <i>d</i> : <i>L</i> × <i>L</i> → <b><a href="Real_number" title="Real number">R</a></b>. Find the <a href="Bijection" title="Bijection">bijection</a> <i>f</i> : <i>P</i> → <i>L</i> ("assignment") such that the cost function:</dd></dl>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{a,b\in P}w(a,b)\cdot d(f(a),f(b))}</annotation>

</semantics>

</math></span><img src="./05d30494a1a27d09c83ad564ccaf41194006d89e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:25.626ex; height:5.843ex;" alt="{\displaystyle \sum _{a,b\in P}w(a,b)\cdot d(f(a),f(b))}" loading="lazy"></span></dd></dl></dd>

<dd>is minimized.</dd></dl>

<p>Usually weight and distance functions are viewed as square real-valued <a href="Matrix_(mathematics)" title="Matrix (mathematics)">matrices</a>, so that the cost function is written down as:

</p>

</mrow>

</munder>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sum _{a,b\in P}w_{a,b}d_{f(a),f(b)}}</annotation>

</semantics>

</math></span><img src="./09e295a571af30b6b12ab12f2910a36d441730ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:16.519ex; height:5.843ex;" alt="{\displaystyle \sum _{a,b\in P}w_{a,b}d_{f(a),f(b)}}" loading="lazy"></span></dd></dl>

<p>In matrix notation:

</p>

<msub>

</mrow>

</msub>

</mrow>

</munder>

<mi>trace</mi>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min _{X\in \Pi _{n}}\operatorname {trace} (WXD^{T}X^{T})}</annotation>

</semantics>

</math></span><img src="./bc38778aa823d6d810855b4420fc0b42f01a8893.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:23.049ex; height:4.676ex;" alt="{\displaystyle \min _{X\in \Pi _{n}}\operatorname {trace} (WXD^{T}X^{T})}" loading="lazy"></span></dd></dl>

<p>where <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pi _{n}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pi _{n}}</annotation>

</semantics>

</math></span><img src="./09f95d02eefa1f08f4a994ebf0d60aad2c122dd9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.962ex; height:2.509ex;" alt="{\displaystyle \Pi _{n}}" loading="lazy"></span> is the set of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\times n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\times n}</annotation>

</semantics>

</math></span><img src="./59d2b4cb72e304526cf5b5887147729ea259da78.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.63ex; height:1.676ex;" alt="{\displaystyle n\times n}" loading="lazy"></span> permutation matrices, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle W}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle W}</annotation>

</semantics>

</math></span><img src="./54a9c4c547f4d6111f81946cad242b18298d70b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.435ex; height:2.176ex;" alt="{\displaystyle W}" loading="lazy"></span> is the weight matrix and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle D}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle D}</annotation>

</semantics>

</math></span><img src="./f34a0c600395e5d4345287e21fb26efd386990e6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.924ex; height:2.176ex;" alt="{\displaystyle D}" loading="lazy"></span> is the distance matrix.

</p>

<div class="mw-heading mw-heading2"><h2 id="Computational_complexity">Computational complexity</h2></div>

<p>The problem is <a href="NP-hard" class="mw-redirect" title="NP-hard">NP-hard</a>, so there is no known <a href="Algorithm" title="Algorithm">algorithm</a> for solving this problem in <a href="Time_complexity" title="Time complexity">polynomial time</a>, and even small instances may require long computation time. It was also proven that the problem does not have an approximation algorithm running in polynomial time for any (constant) factor, unless P = NP.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> The <a href="Travelling_salesman_problem" title="Travelling salesman problem">travelling salesman problem</a> (TSP) may be seen as a special case of QAP if one assumes that the flows connect all facilities only along a single ring, all flows have the same non-zero (constant) value and all distances are equal to the respective distances of the TSP instance. Many other problems of standard <a href="Combinatorial_optimization" title="Combinatorial optimization">combinatorial optimization</a> problems may be written in this form.

</p>

<div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2></div>

<p>In addition to the original plant location formulation, QAP is a mathematical model for the problem of placement of interconnected <a href="Electronic_component" title="Electronic component">electronic components</a> onto a <a href="Printed_circuit_board" title="Printed circuit board">printed circuit board</a> or on a <a href="Integrated_circuit" title="Integrated circuit">microchip</a>, which is part of the <a href="Place_and_route" title="Place and route">place and route</a> stage of <a href="Computer_aided_design" class="mw-redirect" title="Computer aided design">computer aided design</a> in the electronics industry.

</p><p>The QAP has also been used to model the cost of character placement on a keyboard. In this case, the locations are keys on the keyboard and their pairwise distances correspond to the time required to press a given pair of keys. The facilities are characters and their weights are proportional to how often the given pair of characters occur in a text corpus. This type of QAP model was used in the design of the French keyboard standard (NF Z71-300).<sup id="cite_ref-t142_3-0" class="reference"><a href="#cite_note-t142-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<ul><li><a href="Quadratic_bottleneck_assignment_problem" title="Quadratic bottleneck assignment problem">Quadratic bottleneck assignment problem</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">Koopmans TC, Beckmann M (1957). Assignment problems and the location of economic activities. Econometrica 25(1):53-76</span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFSahniGonzalez1976" class="citation journal cs1">Sahni, Sartaj; Gonzalez, Teofilo (July 1976). "P-Complete Approximation Problems". <i>Journal of the ACM</i>. <b>23</b> (3): <span class="nowrap">555–</span>565. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F321958.321975">10.1145/321958.321975</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/10338.dmlcz%2F103883">10338.dmlcz/103883</a></span>.</cite></span>

</li>

<li id="cite_note-t142-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-t142_3-0">^</a></b></span> <span class="reference-text"><cite id="CITEREFJohnKarrenbauer2019" class="citation book cs1">John, Maximilian; Karrenbauer, Andreas (2019). "Dynamic Sparsification for Quadratic Assignment Problems". <a rel="nofollow" class="external text" href="https://resources.mpi-inf.mpg.de/keyboardoptimization/MOTOR2019/MOTOR2019.pdf"><i>Mathematical Optimization Theory and Operations Research</i></a> <span class="cs1-format">(PDF)</span>. Vol. 11548. Cham: Springer International Publishing. p. 232–246. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-030-22629-9_17">10.1007/978-3-030-22629-9_17</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-030-22628-2</bdi>.</cite></span>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="Other_sources">Other sources</h2></div>

<ul><li><cite id="CITEREFMichael_R._Garey_and_David_S._Johnson1979" class="citation book cs1"><a href="Michael_R._Garey" class="mw-redirect" title="Michael R. Garey">Michael R. Garey</a> and <a href="David_S._Johnson" title="David S. Johnson">David S. Johnson</a> (1979). <a href="Computers_and_Intractability%3A_A_Guide_to_the_Theory_of_NP-Completeness" class="mw-redirect" title="Computers and Intractability: A Guide to the Theory of NP-Completeness"><i>Computers and Intractability: A Guide to the Theory of NP-Completeness</i></a>. W.H. Freeman. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-7167-1045-5</bdi>.</cite> A2.5: ND43, pg.218.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external free" href="https://doi.org/10.7488/ds/3428">https://doi.org/10.7488/ds/3428</a> QAPLIB - A Quadratic Assignment Problem Library</li>

<li><a rel="nofollow" class="external free" href="http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/">http://www.wiomax.com/team/xie/maos-qap-quadratic-assignment-problem-project-portal/</a> MAOS-QAP - Java-based Quadratic Assignment Problem Solver</li>

<li><a rel="nofollow" class="external free" href="https://CRAN.R-project.org/package=qap">https://CRAN.R-project.org/package=qap</a> - R package qap: Heuristics for the Quadratic Assignment Problem</li>

<li><a rel="nofollow" class="external free" href="https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ">https://apps.microsoft.com/store/detail/qapsolver/9N7WMCFB6NZZ</a> - Metaheuristic QAP solver for Windows 10/11</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-04-16" href="https://en.wikipedia.org/wiki/?title=Quadratic_assignment_problem&oldid=1285817418">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>